package com.zhanghp.class036;

import com.zhanghp.common.TreeNode;

/**
 * 验证完全二叉树<br/>
 * 测试链接 : https://leetcode.cn/problems/check-completeness-of-a-binary-tree/
 *
 * @author zhanghp
 * @since 2024/4/19 10:50
 */
public class Code08_CompletenessOfBinaryTree {
    static class Solution {

        public int MAXN = 3001;
        public TreeNode[] queue = new TreeNode[MAXN];
        public int l, r;

        public boolean isCompleteTree(TreeNode root) {
            if (root == null) {
                return true;
            }
            l = r = 0;
            queue[r ++] = root;
            // 是否遇到过左右两个孩子不双全的节点
            boolean leaf = false;
            // 层层（左-》右）遍历，然后判断是否是叶子
            while (l < r){
                TreeNode node = queue[l++];
                // 1.左为null，右不为null
                // 2.是叶子结点，说明node老爸的左孩子为叶子结点（因为层层从左到右遍历），所以该结点不能有左右孩子
                if ((node.left == null && node.right !=null) || (leaf && (node.left != null ||node.right != null))) {
                    return false;
                }
                if (node.left != null) {
                    queue[r ++] = node.left;
                }
                if (node.right != null) {
                    queue[r ++] = node.right;
                }
                // 或关系原因：比如根节点左孩子有左节点，那么根的右孩子不能有任何左右节点
                if (node.left == null || node.right == null) {
                    leaf = true;
                }
            }
            return true;
        }
    }

}
